package com.zyk.grate_offer.class01;

import java.util.HashMap;

/**
 * 给定一个数组arr，你可以在每个数字之前决定+或者-
 * 但是必须所有数字都参与
 * 再给定一个数target，请问最后算出target的方法数是多少？
 * @author zhangsan
 * @date 2021/4/21 11:04
 */
public class Code07_TargetSum {

    // 暴力解
    public static int findTargetSumWays1(int[] nums, int target) {
        return process(nums, 0, target);
    }

    public static int process(int[] arr, int i, int rest) {
        if(i == arr.length) return rest == 0 ? 1 : 0;
        int p1 = process(arr, i+1 , rest - arr[i]);
        int p2 = process(arr, i+1 , rest + arr[i]);
        return p1 + p2;
    }

    // 改记忆化搜索
    public static int findTargetSumWays2(int[] nums, int target) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++)
            sum += nums[i];

        if(sum < target || ((sum&1) ^ (target&1)) == 1 ) return 0;  // 如果所有数累加和还不够target或, 最后累加和和target奇偶不一样 return 0种方法
        return process1(nums, 0, target, new HashMap<>());
    }

    // 因为rest可以是负数, 数组的二维表不好建,建出来用的是还又要+逻辑,干脆就用map做
    private static int process1(int[] arr, int i, int rest, HashMap<Integer, HashMap<Integer, Integer>> dp) {
        if(dp.containsKey(i) && dp.get(i).containsKey(rest)) return dp.get(i).get(rest);
        if(i == arr.length) return rest == 0 ? 1 : 0;
        int ans = process1(arr, i+1 , rest - arr[i], dp)+ process1(arr, i+1 , rest + arr[i], dp);
        if(!dp.containsKey(i)) dp.put(i, new HashMap<>());
        dp.get(i).put(rest, ans);
        return ans;
    }

    // 优化点一 :
    // 你可以认为arr中都是非负数
    // 因为即便是arr中有负数，比如[3,-4,2]
    // 因为你能在每个数前面用+或者-号
    // 所以[3,-4,2]其实和[3,4,2]达成一样的效果
    // 那么我们就全把arr变成非负数，不会影响结果的
    // 优化点二 :
    // 如果arr都是非负数，并且所有数的累加和是sum
    // 那么如果target<sum，很明显没有任何方法可以达到target，可以直接返回0
    // 优化点三 :
    // 因为题目要求一定要使用所有数字去拼target，
    // 所以不管这些数字怎么用+和-折腾，最终的结果都一定不会改变奇偶性
    // 所以，如果所有数的累加和是sum，
    // 并且与target的奇偶性不一样，没有任何方法可以达到target，可以直接返回0
    // 优化点四 :
    // 比如说给定一个数组, arr = [1, 2, 3, 4, 5] 并且 target = 3
    // 其中一个方案是 : +1 -2 +3 -4 +5 = 3
    // 该方案中取了正的集合为P = {1，3，5}
    // 该方案中取了负的集合为N = {2，4}
    // 所以任何一种方案，都一定有 sum(P) - sum(N) = target
    // 现在我们来处理一下这个等式，把左右两边都加上sum(P) + sum(N)，那么就会变成如下：
    // sum(P) - sum(N) + sum(P) + sum(N) = target + sum(P) + sum(N)
    // 2 * sum(P) = target + 数组所有数的累加和
    // sum(P) = (target + 数组所有数的累加和) / 2
    // 也就是说，任何一个集合，只要累加和是(target + 数组所有数的累加和) / 2
    // 那么就一定对应一种target的方式
    // 也就是说，比如非负数组arr，target = 7, 而所有数累加和是11
    // 求使用所有数字的情况下，多少方法最后形成7？
    // 其实就是求有多少个子集的累加和是9 -> (7 + 11) / 2
    // 优化点五 :
    // 二维动态规划的空间压缩技巧
    public static int findTargetSumWays3(int[] arr, int s) {
        int sum = 0;
        for (int n : arr) {
            sum += n;
        }
        return sum < s || ((s & 1) ^ (sum & 1)) != 0 ? 0 : subset(arr, (s + sum) >> 1);
    }

    public static int subset(int[] nums, int s) {
        int[] dp = new int[s + 1];
        dp[0] = 1;
        for (int n : nums) {
            for (int i = s; i >= n; i--) {
                dp[i] += dp[i - n];
            }
        }
        return dp[s];
    }


    // for test
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        int target = 3;
        System.out.println(findTargetSumWays1(arr, target));
        System.out.println(findTargetSumWays2(arr, target));
        System.out.println(findTargetSumWays3(arr, target));

    }

}
